1. Field of Art
The present invention relates to packet exchange networks and, more specifically, to apparatuses and methods for selectively discarding data packets in packet exchange networks in order to meet quality of service performance requirements for multiple data traffic streams having a diverse range of data and transmission characteristics.
2. Related Art
In integrated packet exchange networks, it is often desirable or necessary to manage network resources to meet different quality-of-service (QoS) requirements for multiple traffic streams and flows. In practice, this constitutes a major challenge for network operators because different traffic streams may have vastly different data characteristics and QoS requirements. In an effort to realize optimum QoS performance for multiple and diverse traffic streams, various data traffic management mechanisms have been proposed, most of which attempt to minimize data packet losses and delays as data packets travel from source nodes to destination nodes in the packet exchange network. Usually, although not necessarily, these mechanisms employ some form of priority-based or measurement-based service or loss scheduling.
Service and loss scheduling are typically applied to packet buffer pools waiting to use a limited network resource. Such packet buffer pools may be found, for example, at queues, inputs and outputs to packet switches or packet switch processors, and at queues, inputs and outputs to communications channels for packet switches. Packet buffer pools may also be found in network switches, routers, multiplexers, or any other node or device in a packet exchange network having data packet buffers configured to receive and store data packets from multiple distinguishable data streams and flows. As a result of network traffic congestion, a buffer pool or communication channel may become fully occupied, in which case it becomes necessary to selectively schedule data packet transmissions or selectively discard packets when there are new packet arrivals.
Two types of priority-based traffic management mechanisms are time-priority and space-priority. Time priority mechanisms are typically implemented by employing some form of selective service scheduling for each communication channel in the packet exchange network. That is, whenever a communications channel completes transmitting a packet (also called a “cell” in asynchronous transfer mode networks), a priority rule is applied to determine which packet should be transmitted next. Fair queuing (FQ) is a well-known example of a service-scheduling mechanism that could be employed in an effort to achieve a higher end-to-end QoS performance in networks where, in the interest of fairness, the goal is to give multiple traffic streams substantially equal access to limited network resources. Another approach is to use weighted fair queuing (WFQ), where the goal is to give multiple traffic streams access to limited network resources in proportion to an assigned weight.
Space-priority mechanisms, on the other hand, are typically implemented by employing some form of selective loss scheduling, which discards selected data packets based on priority. Various selective packet discard mechanisms have been proposed to discard packets intelligently in an effort towards achieving the goal of meeting the end-to-end loss requirements of individual traffic flows or providing fairness among traffic flows in accessing limited network resources. Hitherto proposed selective discard mechanisms include, for example: the push-out scheme presented in H. J. Chao & H. Cheng, A New QoS-Guaranteed Cell Discarding Strategy: Self-Calibrating Pushout, in Proc. IEEE Globecom '94, pp. 929-934, San Francisco, Calif. 1994; the partial buffer sharing (PBS) scheme presented in H. Kroner, G. Hebuterne, P. Boyer & A. Gravey, Priority Management in ATM Switching Nodes, IEEE Journal on Selected Areas of Communications, Vol. 9, No. 3, pp. 418-427, April 1991; the weighted fair blocking (WFB) schemes presented in A. E. Conway & C. Rosenburg, Weighted Fair Blocking Mechanisms for Discrete-Time Multiplexing, in Proc. IEEE Infocom '96, pp. 1045-1053, San Francisco, Calif. 1996 and A. E. Conway & C. Rosenburg, A Simple Balanced Fair Blocking Mechanism for Discrete Time Multiplexing of Bursty Traffic Sources; in Proc. IEEE ICCCN '1999, pp. 36-41, Boston, Mass. October 1999; and the packet discard scheme disclosed in U.S. Pat. No. 5,444,706, entitled “Packet Exchange Network and Method of Controlling Discard of Packets in Packet Exchange Network.” Each of these references is incorporated herein by reference in its entirety.
Measurement-based loss scheduling schemes involve the on-line measurement and maintenance of packet loss ratios for each traffic stream. When a data packet (or cell) arrives at a packet buffer that is already full, measurement-based loss scheduling schemes identify and discard a packet that belongs to the traffic stream with the smallest ratio between its loss ratio measurement and the traffic stream's specified maximum loss requirement. One such measurement-based loss-scheduling scheme is presented by T. Yang & J. Pan, A Measurement-Based Loss Scheduling Scheme, Proc. IEEE Infocom '96, pp. 1062-1071, San Francisco, 1996, the entirety of which is also incorporated herein by reference.
A common disadvantage of conventional selective packet discard mechanisms is that the decision regarding the choice of packets to be discarded in the event of packet buffer congestion is based solely on information that is available at the packet switching node making the discard decision. Such local information may include, for example, the QoS requirement of each traffic flow, the number of received packets in each traffic flow, and the number of packets in each traffic flow that have been discarded at the local packet switch. Such local information does not include the packet loss that a traffic flow may have already incurred at other upstream packet-switching nodes. Consequently, the local packet discard decisions being made at a packet switch using a conventional selective packet discard mechanism usually do not provide the desired end-to-end packet loss performance or the desired QoS fairness among traffic flows.
In the interest of addressing these and other problems associated with conventional selective discard mechanisms, the industry needs a more intelligent system for selectively discarding data packets, which takes into consideration the upstream packet loss already incurred by the data flow at the time the discard decision is made. Such a system would be even more useful if it were adapted to use, in addition to upstream packet loss, the current state of the local packet switching node, as well as a specified discard policy.